﻿#define _CRT_SECURE_NO_WARNINGS  1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


//283.移动零
class Solution1 {
public:
    void moveZeroes(vector<int>& nums)
    {
        int dest = 0;
        int cur = 0;
        for (; cur < nums.size(); cur++)
        {
            if (nums[cur])
            {
                swap(nums[cur], nums[dest++]);
            }
        }
    }
};



//1089.复写零
class Solution2
{
    public:
        void duplicateZeros(vector<int>& arr)
        {
            int cur = 0;
            int dest = -1;
            for (cur = 0; cur < arr.size(); cur++)
            {
                if (arr[cur]) //不是0 往后走一次
                {
                    dest++;
                }
                else  //是0，往后走两次
                {
                    dest += 2;
                }
                if (dest >= arr.size() - 1) //走到结尾了
                {
                    break;
                }
            }


            if (dest == arr.size()) //如果dest是走到结尾结束的
            {
                arr[arr.size() - 1] = 0;   //把最后一位变成0
                cur--; dest -= 2; //cur往前走一位，dest往前走两位
            }

            while (cur >= 0)   // 倒着复写
            {
                if (arr[cur])
                {
                    arr[dest--] = arr[cur--];
                }
                else
                {
                    arr[dest--] = 0;
                    arr[dest--] = 0;
                    cur--;
                }
            }

        }
};


//202.快乐数
class Solution3
{

 public:

    int GetNum(int n)
    {
        int sum = 0;
        while (n)
        {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n)
    {
        int slow = n, fast = GetNum(n);
        while (slow != fast)
        {
            slow = GetNum(slow);
            fast = GetNum(GetNum(fast));
        }

        return slow == 1 ? true : false;
    }
};


//11.盛最多⽔的容器
class Solution4
{
public:
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left < right)
        {
            int v = (right - left) * min(height[left], height[right]);
            ret = max(ret, v);

            //两种情况:1.height[left]已经是min,右边往左找，长减小，高不变，面积减少
            //         2.height[left]不是min，右边往左找，找到min了，此时高减小，长减小，面积自然减小
            //          综上所述，height[left]就不是要找的
            if (height[left] < height[right])    
            {
                left++;
            }
            else
            {
                right--;

            }
        }

        return ret;
    }

};


//611.有效三⻆形的个数
class Solution5
{
public:
    int triangleNumber(vector<int>&nums)
    {
            sort(nums.begin(),nums.end());
            int ret = 0;
            int n = nums.size() - 1;
            for (int i = n; i >= 2; i--)
            {
                int left = 0;
                int right = i - 1;
                while (left < right)
                {
                    if (nums[left] + nums[right] > nums[i])
                    {
                        ret += (right - left);
                        right--;
                    }
                    else
                    {
                        left++;
                    }
                }
            }


            return ret;
    }
};


//剑指Offer 57.和为s的两个数字
class Solution6 {
public:
    vector<int> twoSum(vector<int>& price, int target)
    {

        int n = price.size();
        int left = 0;
        int right = n - 1;
        vector<int> ret;
        while (left < right)
        {
            if (price[left] + price[right] > target)
            {
                right--;
            }
            else if (price[left] + price[right] < target)
            {
                left++;
            }
            else
            {
                ret.push_back(price[left]);
                ret.push_back(price[right]);
                break;
            }
        }


        return ret;
    }
};


//15.三数之和
class Solution7 {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        // -1 0 0 0 1 1 2 3 4 4 4 5 6
        for (int i = 0; i < n;)
        {
            if (nums[i] > 0) break;
            int target = -nums[i];
            int left = i + 1;
            int right = n - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > target) right--;
                else if (nums[left] + nums[right] < target) left++;
                else if (nums[left] + nums[right] == target)
                {
                    ret.push_back({ nums[i],nums[left],nums[right] });
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1])
                    {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1])
                    {
                        right--;
                    }

                }
            }
            i++;
            while (i < n && nums[i] == nums[i - 1])
            {
                i++;
            }
        }

        return ret;
    }
};


//18.四数之和
class Solution8 {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        for (int i = 0; i < n;)
        {
            //-2 -1 0 0 1 1      
            for (int j = i + 1; j < n;)
            {
                int left = j + 1;
                int right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim)  right--;
                    else if (sum < aim) left++;
                    else
                    {
                        ret.push_back({ nums[left], nums[right], nums[i], nums[j] });
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1])   left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }

                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;

        }

        return ret;
    }
};
int main()
{
    Solution8 s;
    vector<int> v{ -3,-1,0,2,4,5 };
    s.fourSum(v,0);

}


